\documentclass[11pt]{article}
\usepackage{url} 
\usepackage{graphicx}    % needed for including graphics e.g. EPS, PS
\topmargin -1.5cm        % read Lamport p.163
\oddsidemargin -0.04cm   % read Lamport p.163
\evensidemargin -0.04cm  % same as oddsidemargin but for left-hand pages
\textwidth 16.59cm
\textheight 21.94cm 
%\pagestyle{empty}       % Uncomment if don't want page numbers
\parskip 7.2pt           % sets spacing between paragraphs
%\renewcommand{\baselinestretch}{1.5} 	% Uncomment for 1.5 spacing between lines
 \parindent 0pt		  % sets leading space for paragraphs

 \begin{document}
 \begin{center}
 \Large{\textbf{COMP 388 - High Performance Computing - Project 1}}
 
 \small{Pawel Grocholski and Marty Heath}
 \end{center}

 \section{Background}
 \label{Background}
Performance has always been an important topic in computer science, and while one might argue that the importance has diminished with the coming of exceptionally powerful commodity processors, benchmarking and profiling remain critical when dealing with the ever growing data sets arising from new domains opened up by this surplus of computational power. Furthermore the understanding of resource use will become even more relevant with the current trend in processor design: multi-, and many-core processors seem to be the future of computer architecture, and that understanding will become essential in scaling problems over these chips.

\section{Methodology}
\label{Methodology}
For this assignment we analyzed the performance of a basic sort of an array of randomly generated integers, measuring the run-time of the algorithm over a range of different array sizes. For the purposes of our project, as implemented in Java, running on OpenJDK Server VM version 14.0-b16, the standard {\it java.util.Array.sort();} method was used, which for integers, uses a tuned quicksort algorithm\cite{javasort}; the array was created, filled with ints using the standard random number generator calling {\it nextInt()}, the time returned by {\it System.currentTimeMillis()} was recorded, the sorting function called upon the array, and upon completion, the time was recorded once more, the difference between the times being printed to the console. This java program was run by a simple shell script which called the program with array sizes which were powers of 2 from $2^8$ to $2^{29}$. Each array size was tested 30 times in order to obtain representative data, with a call to sleep, pausing the script for one second between calls in order to keep the interference by the operating system to a minimum. The test was run on two different systems, a modern laptop running 64 bit Linux and using DDR3 RAM, and another, 1 year old laptop, running 32 bit Linux and using DDR2 RAM, both systems running Arch Linux kernel 2.6.30. 

\section{Results}
\label{Results}
\begin{left}
\includegraphics[scale=0.4]{pauls_data.png}
\includegraphics[scale=0.4]{martys_data.png}
\end{left}
\newline
\begin{center}
\includegraphics[scale=0.6]{combined_data.png} 
\end{center}
\pagebreak

\section{Conclusion}
\label{Conclusion}
The data clearly reflects the expected near-linear runtime trend of O(nlogn), the amortized runtime of the quicksort algorithm. The runtime performance was expected to be such due to the fact that the data, an array of completely random integers, is the ideal dataset to run quicksort on, any non-random set of data would most likely result in a degradation in performance, up to the worst case scenario of O($n^2$). Of course, the algorithm utilized by the Java standard library is not concurrent and could not take advantage of both cores that both test machines offered.  Overall, the data is quite consistent, though the smaller array sizes were harder to measure accurately due to the time it took to perform the sort being so small, so much so that for any number below $2^8$ it was hard to record any time at all. For the larger array sizes, there was also a visible switch of the process from one processor core to the other during the beginning of each run, and while it seems that the switch followed the instantiation of the array, and prior to the timing of the sort, nevertheless, there is a chance that the data has been skewed by the overhead of that switch. There is no doubt that this algorithm could benefit greatly from concurrency, though more testing would need to be done to determine at what grain size would the benefits of utilizing more cores overcome the overhead of processing the data on multiple threads.
 
\begin{thebibliography}{99}
\bibitem{javasort} Sun Microsystems. {\it "sort"}, \underline{Arrays (Java 2 Platform SE 5.0.} 2004. Sun Microsystems, Inc.,
September 13, 2009. http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.html\#sort(int[])
\end{thebibliography}

 

 \end{document}

